﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

using TJDevHouse.Starcraft.Game;

namespace TJDevHouse.Starcraft.MapAnalyser
{
	/// <summary>
	/// Finds paths between locations
	/// </summary>
	public class PathFinder
	{
		/// <summary>
		/// The map analyser
		/// </summary>
		public MapAnalysisController MapAnalysis { get; private set; }

		/// <summary>
		/// The map to find paths on
		/// </summary>
		public Map Map { get; private set; }

		public PathFinder(Map map, MapAnalysisController mapAnalysis)
		{
			Map = map;
			MapAnalysis = mapAnalysis;
		}

		/// <summary>
		/// Calculates the path between 2 walk tiles.
		/// </summary>
		/// <param name="fromTile"></param>
		/// <param name="toTile"></param>
		/// <returns></returns>
		public MapPath FindPath(WalkTile fromTile, WalkTile toTile)
		{
			//check whether we should even bother with the test
			if (!IsPathPossible(fromTile, toTile))
			{
				throw new ArgumentOutOfRangeException("There is no valid path between the supplied tiles");
			}

			//check if the tiles are the same, if so just generate a 1 tile path
			if (fromTile == toTile)
			{
				MapPath path = new MapPath();
				List<WalkTile> r = new List<WalkTile>();
				r.Add(fromTile);
				path.SetRoute(r);
				return path;
			}

			//setup the start and target nodes
			PathFindingNode start = new PathFindingNode(fromTile.X, fromTile.Y);
			PathFindingNode target = new PathFindingNode(toTile.X, toTile.Y);

			//create the open nodes list
			List<PathFindingNode> openNodes = new List<PathFindingNode>();

			//stores nodes which have been looked at
			List<PathFindingNode> closedNodes = new List<PathFindingNode>();

			//index the nodes to ensure only one instance of each
			Dictionary<string, PathFindingNode> nodesIndex = new Dictionary<string, PathFindingNode>();

			//add the start node
			openNodes.Add(start);
			nodesIndex.Add(start.GetCoordHash(), start);

			//add the target node to the index
			nodesIndex.Add(target.GetCoordHash(), target);

			//for benchmarking
			int iterations = 0;

			while (openNodes.Count > 0)
			{
				iterations++;

				//get the best next possible node
				PathFindingNode currentNode = GetNodeWithLowestFScore(openNodes, target);

				//were done if this node is the target node
				if (currentNode == target)
				{
					MapPath path = GeneratePathFromNode(currentNode, closedNodes);
					Console.WriteLine("Route with " + path.Route.Count + " tiles found in " + iterations + " iterations");
					Console.WriteLine("Stored " + nodesIndex.Count + " nodes");
					Console.WriteLine("Processed " + closedNodes.Count + " nodes");
					return path;
				}

				//remove from the open nodes
				openNodes.Remove(currentNode);

				//add to the closed nodes
				closedNodes.Add(currentNode);

				//go through each adjacent node
				foreach (PathFindingNode adjNode in currentNode.GetAdjacentNodes())
				{
					//get the correct instance of adjacent node
					PathFindingNode n = GetCorrectNodeInstance(nodesIndex, adjNode);

					//ignore if on closed list
					if (closedNodes.Contains(n))
					{
						continue;
					}

					//ignore if not a valid tile
					if (!Map.IsValidWalkTileCoord(n.X, n.Y))
					{
						continue;
					}

					//ignore if walk tile is not walkable
					if (!GetWalkTileByNode(n).IsWalkable)
					{
						continue;
					}

					//ignore if build tile the walk tile is on is not walkable
					if (!GetWalkTileByNode(n).BuildTile.IsWalkable)
					{
						continue;
					}
					
					if (!openNodes.Contains(n))
					{
						//add adjacent tile to open list if not already on it
						openNodes.Add(n);

						//check if the node has a parent - the target node won't
						//so need to set it to the current node
						if (n.Parent == null)
						{
							n.Parent = currentNode;
						}
					}
					else
					{
						//if is on open list, check if the G cost of adjacent node is less going through
						//the current node than its current parent
						if (n.G(currentNode) < n.G())
						{
							n.Parent = currentNode;
						}
					}
				}
			}

			throw new ArgumentOutOfRangeException("Could not find path between tiles");
		}

		/// <summary>
		/// Takes a node and runs through the parent chain to generate a
		/// path containing all the walk tiles in the path
		/// </summary>
		/// <param name="node"></param>
		/// <returns></returns>
		public MapPath GeneratePathFromNode(PathFindingNode node)
		{
			MapPath path = new MapPath();

			List<WalkTile> tiles = new List<WalkTile>();

			PathFindingNode n = node;
			do
			{
				WalkTile t = GetWalkTileByNode(n);
				tiles.Add(t);

				n = n.Parent;
			} while (n.Parent != null);

			tiles.Reverse();

			path.SetRoute(tiles);

			return path;
		}

		/// <summary>
		/// Generate a path, including all nodes looked at when generating the path.
		/// 
		/// Use for debuggering.
		/// </summary>
		/// <param name="node"></param>
		/// <param name="lookedAtNodes"></param>
		/// <returns></returns>
		public MapPath GeneratePathFromNode(PathFindingNode node, List<PathFindingNode> lookedAtNodes)
		{
			MapPath path = GeneratePathFromNode(node);
			path.ProcessedNodes = lookedAtNodes;
			return path;
		}

		/// <summary>
		/// Checks the index of nodes to see if the supplied node is in the dictionary.
		/// 
		/// If it is, then will return the node in the index, otherwise will add the
		/// node to the dictionary and return the node.
		/// </summary>
		/// <param name="index"></param>
		/// <param name="toCheck"></param>
		/// <returns></returns>
		public PathFindingNode GetCorrectNodeInstance(Dictionary<string, PathFindingNode> index, PathFindingNode toCheck)
		{
			if (!index.ContainsKey(toCheck.GetCoordHash()))
			{
				index.Add(toCheck.GetCoordHash(), toCheck);
			}

			return index[toCheck.GetCoordHash()];
		}

		/// <summary>
		/// Go through all the nodes in the supplied list and
		/// return the one with the lowest F score.
		/// </summary>
		/// <param name="nodes"></param>
		/// <returns></returns>
		public PathFindingNode GetNodeWithLowestFScore(List<PathFindingNode> nodes, PathFindingNode target)
		{
			//make sure the list has some nodes...
			if (nodes.Count == 0)
			{
				throw new ArgumentException("List of nodes is empty");
			}


			int lowestScore = int.MaxValue;
			PathFindingNode lowestNode = new PathFindingNode(-1, -1);

			foreach (PathFindingNode n in nodes)
			{
				int f = n.F(target);
				if (f < lowestScore)
				{
					lowestScore = f;
					lowestNode = n;
				}
			}

			return lowestNode;
		}

		/// <summary>
		/// Gets the map walk tile specified by the node's coordinates
		/// </summary>
		/// <param name="node"></param>
		/// <returns></returns>
		public WalkTile GetWalkTileByNode(PathFindingNode node)
		{
			return Map.GetWalkTile(node.X, node.Y);
		}

		/// <summary>
		/// Checks the supplied walk tiles and decides whether it is possible
		/// to walk from one to the other.
		/// 
		/// Checks whether they are in the same walkability zone and whether they
		/// are both actually walkable tiles
		/// </summary>
		/// <param name="from"></param>
		/// <param name="to"></param>
		/// <returns></returns>
		public bool IsPathPossible(WalkTile from, WalkTile to)
		{
			//are both tiles walkable
			bool bothWalkable = from.IsWalkable && to.IsWalkable;

			//check whether both are walkable and if they are in the same walkability zone
			return (bothWalkable && MapAnalysis.WalkabilityAnalyser.IsTileWalkableFrom(from, to));
		}
	}
}
